// 402.[单调栈ok]移掉 K 位数字
// https://leetcode-cn.com/problems/remove-k-digits/
//给定一个以字符串表示的非负整数 num，移除这个数中k位数字使得剩下的数字最小
//输入：num = "1432219", k = 3
//输出："1219"
//解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
//输入：num = "10200", k = 1
//输出："200"
//解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
//输入：num = "10", k = 2
//输出："0"
//解释：从原数字移除所有的数字，剩余为空就是 0
#include <bits/stdc++.h>
using namespace std;
#define PF(...) printf(__VA_ARGS__)
class Solution {
 public:
  string removeKdigits(string num, int k) {
    vector<char> stkNum;
    for (size_t i = 0; i < num.length(); i++) {
      while (stkNum.size() > 0 && stkNum.back() > num[i] && k > 0) {
        stkNum.pop_back();
        k--;
      }
      stkNum.push_back(num[i]);
    }
    for (; k > 0 && stkNum.size() > 0; k--) {
      stkNum.pop_back();
    }
    string ans;
    bool bPreZero = true;
    for (auto ch : stkNum) {
      if (bPreZero && ch == '0') continue;
      bPreZero = false;
      ans += ch;
    }
    return ans.length() > 0 ? "0" : ans;
  }
};
int main() {
  Solution sol;
  auto ret = sol.removeKdigits("10", 3);
  printf("%s\n", ret.c_str());
}
